package medium;

import metastructure.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到
 * 链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
 * 注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 
 * 不允许修改链表。
 *
 *  示例 1：
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 *
 *  示例 2：
 * 输入：head = [1,2], pos = 0
 * 输出：返回索引为 0 的链表节点
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 *
 *  示例 3：
 * 输入：head = [1], pos = -1
 * 输出：返回 null
 * 解释：链表中没有环。
 *
 *  提示：
 *  链表中节点的数目范围在范围 [0, 104] 内 
 *  -105 <= Node.val <= 105 
 *  pos 的值为 -1 或者链表中的一个有效索引 
 *
 *  进阶：你是否可以使用 O(1) 空间解决此题？ 
 *  Related Topics 哈希表 链表 双指针 
 *  👍 1262 👎 0
 */
public class L142_环形链表II {

    /**
     * 使用Set,用了额外空间.
     *
     * 执行耗时:4 ms,击败了12.59% 的Java用户
     * 内存消耗:39.4 MB,击败了9.12% 的Java用户
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode tmp = head;
        Set<ListNode> set = new HashSet<>();
        while(tmp != null){
            if (set.contains(tmp)) {
                return tmp;
            } else {
                set.add(tmp);
            }
            tmp = tmp.next;
        }
        return null;
    }

    /**
     * 快慢指针.
     *
     * 快慢指针相遇的时候，res指针出发，
     * 当res指针与慢指针相遇时，res指针指的即为入环点.
     *
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:38.5 MB,击败了56.71% 的Java用户
     */
    public ListNode detectCycles(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode fast = head;
        ListNode slow = head;

        while(fast!= null) {
           slow = slow.next;
           if (fast.next!= null) {
               fast = fast.next.next;
           } else {
               return null;
           }

           if (fast == slow) {
               ListNode res = head;
               while(res!=slow) {
                   res = res.next;
                   slow = slow.next;
               }
               return res;
           }
        }
        return null;
    }
}
